package alibaba.algorithm;

import pojo.ListNode;
import pojo.TreeNode;

import java.util.*;


/**
 * @Author chengshijian
 * @Date 2022/2/9 15:29
 */
public class Solution {

    /**
     * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
     * <p>
     *  
     * <p>
     * 示例:
     * <p>
     * 输入: 1->2->3->4->5->NULL
     * 输出: 5->4->3->2->1->NULL
     *  
     * <p>
     * 限制：
     * <p>
     * 0 <= 节点个数 <= 5000
     * <p>
     *  
     * <p>
     * 注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/
     * <p>
     * 通过次数350,669提交次数471,874
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    private static void printLinkList(ListNode head) {
        for (ListNode p = head; p != null; p = p.next) {
            System.out.println(p.val + " ");
        }
    }

    /**
     * 统计一个数字在排序数组中出现的次数。
     * <p>
     *  
     * <p>
     * 示例 1:
     * <p>
     * 输入: nums = [5,7,7,8,8,10], target = 8
     * 输出: 2
     * 示例 2:
     * <p>
     * 输入: nums = [5,7,7,8,8,10], target = 6
     * 输出: 0
     *  
     * <p>
     * 提示：
     * <p>
     * 0 <= nums.length <= 105
     * -109 <= nums[i] <= 109
     * nums 是一个非递减数组
     * -109 <= target <= 109
     *  
     * <p>
     * 注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
     * <p>
     * 通过次数231,689提交次数433,345
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (target <= nums[i]) {
                if (target == nums[i]) {
                    count++;
                }
            }
        }
        return count;
    }


    public static int search2(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int count = 0;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target) {
                right = mid;
            }
            if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        while (left < nums.length && nums[left++] == target) {
            count++;
        }
        return count;
    }

    public static int search3(int[] nums, int target) {
        int count = 0;
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (target >= nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        int first = left;
        while (first < nums.length && nums[first++] == target) {
            count++;
        }
        int second = left - 1;
        while (second >= 0 && nums[second--] == target) {
            count++;
        }
        return count;
    }

    /**
     * 剑指 Offer 53 - II. 0～n-1中缺失的数字
     * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
     * <p>
     * <p>
     * <p>
     * 示例 1:
     * <p>
     * 输入: [0,1,3]
     * 输出: 2
     * 示例 2:
     * <p>
     * 输入: [0,1,2,3,4,5,6,7,9]
     * 输出: 8
     * <p>
     * <p>
     * 限制：
     * <p>
     * 1 <= 数组长度 <= 10000
     * <p>
     * 通过次数207,355提交次数462,102
     *
     * @param nums
     * @return
     */
    public static int missingNumber(int[] nums) {
        int i = 0;
        for (; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return i;
    }

    public static int missingNumber2(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] != mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    /**
     * 53. 最大子数组和
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     *
     * 子数组 是数组中的一个连续部分。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
     * 输出：6
     * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
     * 示例 2：
     *
     * 输入：nums = [1]
     * 输出：1
     * 示例 3：
     *
     * 输入：nums = [5,4,-1,7,8]
     * 输出：23
     *
     *
     * 提示：
     *
     * 1 <= nums.length <= 105
     * -104 <= nums[i] <= 104
     *
     *
     * 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
     *
     * 通过次数841,402提交次数1,524,798
     *
     */

    /**
     * 超时了
     *
     * @param nums
     * @return
     */
    public static int maxSubArray(int[] nums) {

        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int ret = nums[i];
            if (ret > max) {
                max = ret;
            }
            for (int j = i + 1; j < nums.length; j++) {
                ret += nums[j];
                if (ret > max) {
                    max = ret;
                }
            }
        }
        return max;
    }

    /**
     * 贪心算法
     *
     * @param nums
     * @return
     */
    private static int maxSubArray2(int[] nums) {
        int pre = 0;
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            pre = Math.max(pre + nums[i], nums[i]);
            max = Math.max(pre, max);
        }
        return max;
    }

    /**
     * 92. 反转链表 II
     * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：head = [1,2,3,4,5], left = 2, right = 4
     * 输出：[1,4,3,2,5]
     * 示例 2：
     * <p>
     * 输入：head = [5], left = 1, right = 1
     * 输出：[5]
     * <p>
     * <p>
     * 提示：
     * <p>
     * 链表中节点数目为 n
     * 1 <= n <= 500
     * -500 <= Node.val <= 500
     * 1 <= left <= right <= n
     * <p>
     * <p>
     * 进阶： 你可以使用一趟扫描完成反转吗？
     * <p>
     * 通过次数246,545提交次数447,279
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public static ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode leftHead = null;
        ListNode preHead = null;
        int index = 0;
        for (ListNode p = head; p != null; p = p.next) {
            if (++index == left) {
                leftHead = p;
                break;
            }
            preHead = p;
        }
        ListNode pre = null;
        ListNode cur = leftHead;
        ListNode next = cur.next;
        while (cur != null && index++ <= right) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        leftHead.next = next;
        if (preHead != null) {
            preHead.next = pre;
        } else {
            head = pre;
        }
        return head;
    }

    /**
     * 44. 通配符匹配
     * 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
     * <p>
     * '?' 可以匹配任何单个字符。
     * '*' 可以匹配任意字符串（包括空字符串）。
     * 两个字符串完全匹配才算匹配成功。
     * <p>
     * 说明:
     * <p>
     * s 可能为空，且只包含从 a-z 的小写字母。
     * p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
     * 示例 1:
     * <p>
     * 输入:
     * s = "aa"
     * p = "a"
     * 输出: false
     * 解释: "a" 无法匹配 "aa" 整个字符串。
     * 示例 2:
     * <p>
     * 输入:
     * s = "aa"
     * p = "*"
     * 输出: true
     * 解释: '*' 可以匹配任意字符串。
     * 示例 3:
     * <p>
     * 输入:
     * s = "cb"
     * p = "?a"
     * 输出: false
     * 解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
     * 示例 4:
     * <p>
     * 输入:
     * s = "adceb"
     * p = "*a*b"
     * 输出: true
     * 解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
     * 示例 5:
     * <p>
     * 输入:
     * s = "acdcb"
     * p = "a*c?b"
     * 输出: false
     * 通过次数94,263提交次数285,592
     */
//    public static boolean isMatch(String s, String p) {
//        if (p.equals("*")) {
//            return true;
//        }
//        int i = 0;
//        StringBuilder builder = new StringBuilder();
//        while (i < p.length()) {
//            char c = p.charAt(i);
//            if (c != '?' && c != '*') {
//                while (c != '?' && c != '*' && i < p.length()) {
//                    builder.append(c);
//                    i++;
//                    if (i < p.length()) {
//                        c = p.charAt(i);
//                    }
//                }
//                if (s.startsWith(builder.toString())) {
//                    s = s.replaceFirst(builder.toString(), "");
//                    builder.delete(0, builder.length());
////                    i++;
//                } else {
//                    return false;
//                }
//            } else if (c == '?') {
//                if (s.startsWith(builder.toString())) {
//                    s = s.replaceFirst(builder.toString(), "");
//                    builder.delete(0, builder.length());
//                    s = s.replace(String.valueOf(s.charAt(0)), "");
//                    i++;
//                } else {
//                    return false;
//                }
//            } else if (c == '*') {
//                if (++i < p.length()) {
////                    c = p.charAt(i);
////                    int index = s.indexOf(c);
////                    s = s.replaceFirst(s.substring(0, index + 1), "");
////                    i++;
//                } else {
//                    return true;
//                }
//            }
//        }
//        return s.length() == 0;
//    }
    private int depth(TreeNode T) {
        if (T == null) {
            return 0;
        }
        return Math.max(depth(T.left), depth(T.right)) + 1;
    }

    /**
     * 110. 平衡二叉树
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     * <p>
     * 本题中，一棵高度平衡二叉树定义为：
     * <p>
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：root = [3,9,20,null,null,15,7]
     * 输出：true
     * 示例 2：
     * <p>
     * <p>
     * 输入：root = [1,2,2,3,3,null,null,4,4]
     * 输出：false
     * 示例 3：
     * <p>
     * 输入：root = []
     * 输出：true
     * <p>
     * <p>
     * 提示：
     * <p>
     * 树中的节点数在范围 [0, 5000] 内
     * -104 <= Node.val <= 104
     * 通过次数300,587提交次数530,945
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(depth(root.left) - depth(root.right)) > 1) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }

    /**
     * 94. 二叉树的中序遍历
     * 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：root = [1,null,2,3]
     * 输出：[1,3,2]
     * 示例 2：
     * <p>
     * 输入：root = []
     * 输出：[]
     * 示例 3：
     * <p>
     * 输入：root = [1]
     * 输出：[1]
     * 示例 4：
     * <p>
     * <p>
     * 输入：root = [1,2]
     * 输出：[2,1]
     * 示例 5：
     * <p>
     * <p>
     * 输入：root = [1,null,2]
     * 输出：[1,2]
     * <p>
     * <p>
     * 提示：
     * <p>
     * 树中节点数目在范围 [0, 100] 内
     * -100 <= Node.val <= 100
     * <p>
     * <p>
     * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
     * <p>
     * 通过次数678,038提交次数896,206
     */
    private void inTraverse(TreeNode root, List<Integer> resultList) {
        if (!Objects.isNull(root)) {
            inTraverse(root.left, resultList);
            resultList.add(root.val);
            inTraverse(root.right, resultList);
        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> resultList = new ArrayList<>();
        inTraverse(root, resultList);
        return resultList;
    }

    /**
     * 143. 重排链表
     * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
     * <p>
     * L0 → L1 → … → Ln - 1 → Ln
     * 请将其重新排列后变为：
     * <p>
     * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
     * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * <p>
     * 输入：head = [1,2,3,4]
     * 输出：[1,4,2,3]
     * 示例 2：
     * <p>
     * <p>
     * <p>
     * 输入：head = [1,2,3,4,5]
     * 输出：[1,5,2,4,3]
     * <p>
     * <p>
     * 提示：
     * <p>
     * 链表的长度范围为 [1, 5 * 104]
     * 1 <= node.val <= 1000
     * 通过次数149,681提交次数238,025
     *
     * @param head
     */
    public static void reorderList(ListNode head) {
        List<ListNode> nodeList = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next) {
            nodeList.add(p);
        }
        int nodeLength = nodeList.size();
        ListNode p = head;
        for (int i = 0; i < nodeLength / 2; i++) {
            ListNode first = nodeList.get(i);
            if (p != head) {
                p.next = first;
            }
            ListNode second = nodeList.get(nodeLength - i - 1);
            first.next = second;
            p = second;
        }
        if (nodeLength % 2 != 0) {
            ListNode node = nodeList.get(nodeLength / 2);
            p.next = node;
            node.next = null;
        } else {
            p.next = null;
        }
    }

    /**
     * 617. 合并二叉树
     * 给你两棵二叉树： root1 和 root2 。
     * <p>
     * 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
     * <p>
     * 返回合并后的二叉树。
     * <p>
     * 注意: 合并过程必须从两个树的根节点开始。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
     * 输出：[3,4,5,5,4,null,7]
     * 示例 2：
     * <p>
     * 输入：root1 = [1], root2 = [1,2]
     * 输出：[2,2]
     * <p>
     * <p>
     * 提示：
     * <p>
     * 两棵树中的节点数目在范围 [0, 2000] 内
     * -104 <= Node.val <= 104
     * 通过次数228,155提交次数289,676
     *
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        root1.val = root1.val + root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }

    /**
     * 102. 二叉树的层序遍历
     * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：root = [3,9,20,null,null,15,7]
     * 输出：[[3],[9,20],[15,7]]
     * 示例 2：
     * <p>
     * 输入：root = [1]
     * 输出：[[1]]
     * 示例 3：
     * <p>
     * 输入：root = []
     * 输出：[]
     * <p>
     * <p>
     * 提示：
     * <p>
     * 树中节点数目在范围 [0, 2000] 内
     * -1000 <= Node.val <= 1000
     * 通过次数473,592提交次数735,776
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return Collections.EMPTY_LIST;
        }
        List<List<Integer>> resultList = new ArrayList<>();

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int currentLevelSize = queue.size();
            List<Integer> itemList = new ArrayList<>();
            for (int i = 0; i < currentLevelSize; i++) {
                TreeNode node = queue.poll();
                itemList.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            resultList.add(itemList);
        }
        return resultList;
    }

    /**
     * 剑指 Offer 39. 数组中出现次数超过一半的数字
     * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     * <p>
     * <p>
     * <p>
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     * <p>
     * <p>
     * <p>
     * 示例 1:
     * <p>
     * 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
     * 输出: 2
     * <p>
     * <p>
     * 限制：
     * <p>
     * 1 <= 数组长度 <= 50000
     * <p>
     * <p>
     * <p>
     * 注意：本题与主站 169 题相同：https://leetcode-cn.com/problems/majority-element/
     * <p>
     * <p>
     * <p>
     * 通过次数194,212提交次数279,175
     */
    public static int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.compute(nums[i], (k, v) -> v == null ? 1 : v + 1);
        }
        for (Integer k : map.keySet()) {
            if (map.get(k) > nums.length / 2) {
                return k;
            }
        }
        return Integer.MIN_VALUE;
    }

    public static void simpleBubbleSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[j - 1]) {
                    int t = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = t;
                }
            }
        }
    }

    private static void bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            boolean flag = false;
            for (int j = nums.length - 1; j > i; j--) {
                if (nums[j - 1] > nums[j]) {
                    int t = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = t;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }

    public static int majorityElement2(int[] nums) {
        bubbleSort(nums);
        return nums[nums.length / 2];
    }

    /**
     * 215. 数组中的第K个最大元素
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     * <p>
     * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     * <p>
     * <p>
     * <p>
     * 示例 1:
     * <p>
     * 输入: [3,2,1,5,6,4] 和 k = 2
     * 输出: 5
     * 示例 2:
     * <p>
     * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
     * 输出: 4
     * <p>
     * <p>
     * 提示：
     * <p>
     * 1 <= k <= nums.length <= 104
     * -104 <= nums[i] <= 104
     * 通过次数518,904提交次数801,969
     *
     * @param nums
     * @param k
     * @return
     */
    public static int findKthLargest(int[] nums, int k) {
        //冒泡排序
        for (int i = 0; i < nums.length - 1; i++) {
            boolean flag = false;
            for (int j = nums.length - 1; j > i; j--) {
                if (nums[j - 1] < nums[j]) {
                    int t = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = t;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
        return nums[k - 1];
    }

    public static int findKthLargest2(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < nums.length; i++) {
            queue.offer(nums[i]);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        return queue.peek();
    }

    public static void main(String[] args) {

        int[] arr = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(findKthLargest2(arr, 2));
//        System.out.println(majorityElement(arr));


//        System.out.println(isMatch("abcabczzzde", "*abc???de*"));
//
//        int[] arr = new int[]{};
//        System.out.println(maxSubArray(arr));
//        ListNode node1 = new ListNode(1);
//        ListNode node2 = new ListNode(2);
//        ListNode node3 = new ListNode(3);
//        ListNode node4 = new ListNode(4);
//        ListNode node5 = new ListNode(5);
//////
////        node1.next = node2;
////        node2.next = null;
//        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        node4.next = node5;
//        node5.next = null;
////
//        printLinkList(node1);
//        System.out.println("---------------------");
////
//        reorderList(node1);
////
//        printLinkList(node1);

    }

}




